|
In the mathematics of permutations and the study of shuffling playing cards, a riffle shuffle permutation is one of the permutations of a set of ''n'' items that can be obtained by a single riffle shuffle, in which a sorted deck of ''n'' cards is cut into two packets and then the two packets are interleaved (e.g. by moving cards one at a time from the bottom of one or the other of the packets to the top of the sorted deck). As a special case of this, a (''p'',''q'')-shuffle, for numbers ''p'' and ''q'' with ''p'' + ''q'' = ''n'', is a riffle in which the first packet has ''p'' cards and the second packet has ''q'' cards.〔Weibel, Charles (1994). ''An Introduction to Homological Algebra'', p. 181. Cambridge University Press, Cambridge.〕 ==Combinatorial enumeration== Since a (''p'',''q'')-shuffle is completely determined by how its first ''p'' elements are mapped, the number of (''p'',''q'')-shuffles is : The wedge product of a ''p''-form and a ''q''-form can be defined as a sum over (''p'',''q'')-shuffles.〔 However, the number of distinct riffles is not quite the sum of this formula over all choices of ''p'' and ''q'' adding to ''n'' (which would be ''2''''n''), because the identity permutation can be represented in multiple ways as a (''p'',''q'')-shuffle for different values of ''p'' and ''q''. Instead, the number of distinct riffle shuffle permutations of a deck of ''n'' cards, for ''n'' = 1, 2, 3, ..., is :1, 2, 5, 12, 27, 58, 121, 248, 503, 1014, ... More generally, the formula for this number is 2''n'' − ''n''; for instance, there are 4503599627370444 riffle shuffle permutations of a 52-card deck. The number of permutations that are both a riffle shuffle permutation and the inverse permutation of a riffle shuffle is〔.〕 : For ''n'' = 1, 2, 3, ..., this is :1, 2, 5, 11, 21, 36, 57, 85, 121, 166, 221, ... and for ''n'' = 52 there are exactly 23427 invertible shuffles. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Riffle shuffle permutation」の詳細全文を読む スポンサード リンク
|